package algocasts;

import java.util.Stack;

/**
 * 判断二叉树是否相同
 */
public class P8_isSameTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }

    // 递归
    public boolean isSameTree_recursive(TreeNode p, TreeNode q) {
        // 两个节点都为空，返回true
        if (p == null && q == null) return true;
        // 一个为空一个不为空，肯定不相同，返回false
        if (p == null || q == null) return false;
        return
                // 两节点值相同
                p.val == q.val &&
                // 比较两节点的左子树
                isSameTree_recursive(p.left, q.left) &&
                // 比较两节点的右子树
                isSameTree_recursive(p.right, q.right);
    }

    // 栈迭代
    public boolean isSameTree_Iterative(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(p);  // 两个节点入栈
        stack.push(q);
        while (!stack.isEmpty()) {
            // 对比的两个节点出栈
            TreeNode left = stack.pop(), right = stack.pop();
            // 两个节点都为空，下一层循环继续对比
            if (left == null && right == null) continue;
            // 一空一不空，false
            if (left == null || right == null) return false;
            // 都非空但是值不相等，false
            if (left.val != right.val) return false;
            // 要对比的两节点相邻入栈
            stack.push(left.left);
            stack.push(right.left);
            stack.push(left.right);
            stack.push(right.right);
        }
        return true;
    }
}
